package com.wkh.datastructure.BSTTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉搜索树
 */
public class BSTTree<T extends Comparable<T>,V> {
    //节点类
    public static class BSTNode<T,V>{
        T key;
        V value;
        BSTNode<T,V> left;
        BSTNode<T,V> right;

        public BSTNode(T key, V value) {
            this.key = key;//key值唯一
            this.value = value;
        }

        public BSTNode(T key) {
            this.key = key;
        }

        public BSTNode(T key, V value, BSTNode<T,V> left, BSTNode<T,V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    //根节点
    public BSTNode<T,V> root;
    /*public Object get(T key){
        return doGet(root,key);
    }

    private Object doGet(BSTNode<T> node, T key) {
        if (node == null){
            return null;
        }
        if (key<node.key){
            return doGet(node.left,key);//向左找
        }else if (key>node.key){
            return doGet(node.right,key);//向右找
        }else {
            return node.value;//找到了
        }
    }*/
    //非递归方式
    public V get(T key){
        if (key == null){
            throw new IllegalArgumentException("参数错误");
        }
        BSTNode<T,V> node = this.root;
       /* while (node != null){
            if (key<node.key){
                node = node.left;
            }else if (key>node.key){
                node = node.right;
            }else {
                return node.value;
            }
        }*/

        while (node != null){
            /**
             * -1 key<node.key
             * 0 key == node.key
             * 1 key > node.key
             */
            int result = key.compareTo(node.key);
            if (result<0){
                node = node.left;
            }else if (result>0){
                node = node.right;
            }else{
                return node.value;
            }
        }
        return null;
    }

    /*public V min(){
       return doMin(root);
    }

    private V doMin(BSTNode<T, V> node) {
        if (node == null){
            return null;
        }
        if (node.left == null){
            return node.value;
        }
        return doMin(node.left);
    }*/
    //非递归版的实现
    public V min(){
        return getMin(root);
    }

    private V getMin(BSTNode<T, V> node) {
        while (node.right!=null){
            node = node.right;
        }
        return node.value;
    }

    public V max(){
        return getMax(root);
    }

    private V getMax(BSTNode<T, V> node) {
        if (node == null){
            return null;
        }
        while (node.right!=null){
            node = node.right;
        }
        return node.value;
    }

    public void put(T key,V value){
        BSTNode<T, V> node = this.root;
        //如果为空节点
        if (node == null){
            root = new BSTNode<T,V>(key,value);
            return;
        }
        BSTNode<T, V> parent = null;
        while (node!=null){
            parent = node;
            int result = key.compareTo(node.key);
            if (result<0){
                node = node.left;
            }else if (result > 0){
                node = node.right;
            }else{
                //1.key存在更新value
                node.value = value;
                return;
            }
        }

        //2.key不存在新增key
        int result = key.compareTo(parent.key);
        if (result < 0){
            parent.left = new BSTNode<T,V>(key,value);
        }else if (result > 0){
            parent.right = new BSTNode<T,V>(key,value);
        }
    }
    //获取前驱
   public V predecessor(T key){
       /**
        * 情况1：节点有左子树，此时前驱就是左子树的最大值
        * 情况2：节点没有左子树，若离它最近的、自左而来的祖先就是前驱
        */
       BSTNode<T,V> p = root;
       //自左而来的祖先节点
       BSTNode<T,V> ancestorFromLeft = null;
       while (p != null){
           int result = key.compareTo(p.key);
           if (result<0){
               p = p.left;
           }else if (result > 0){
               ancestorFromLeft = p;
               p = p.right;
           }else{
               break;
           }
       }
       //没有找到该节点
       if (p == null){
           return null;
       }
       //情况1：节点有左子树，此时前驱就是左子树的最大值
       if (p.left!=null){
           return getMax(p.left);
       }
       //情况2：节点没有左子树，若离它最近的、自左而来的祖先就是前驱
       return ancestorFromLeft == null ? null : ancestorFromLeft.value;
   }
   //获取后继
    public V successor(T key){
        /**
         * 情况1：节点有左子树，此时前驱就是左子树的最大值
         * 情况2：节点没有左子树，若离它最近的、自左而来的祖先就是前驱
         */
        BSTNode<T,V> p = root;
        //自右而来的祖先节点
        BSTNode<T,V> ancestorFromRight = null;
        while (p != null){
            int result = key.compareTo(p.key);
            if (result<0){
                ancestorFromRight = p;
                p = p.left;
            }else if (result > 0){
                p = p.right;
            }else{
                break;
            }
        }
        //没有找到该节点
        if (p == null){
            return null;
        }
        //情况1：节点有右子树，此时后继就是右子树的最小值
        if (p.right!=null){
            return getMin(p.right);
        }
        //情况2：节点没有右子树，若离它最近的、自右而来的祖先就是后继
        return ancestorFromRight == null ? null : ancestorFromRight.value;
    }

    public V delete(T key){
        if (key == null){
            return null;
        }
        BSTNode<T,V> p = root;
        BSTNode<T,V> parent = null;
        while (p != null){
            int result = key.compareTo(p.key);
            if (result<0){
                parent = p;
                p = p.left;
            }else if (result>0){
                parent = p;
                p = p.right;
            }else{
                break;
            }
        }
        //没找到
        if (p == null){
            return null;
        }

        if (p.left != null && p.right == null) {
            shift(parent,p,p.left);
        } else if (p.right != null && p.left == null) {
            shift(parent,p,p.right);
        } else if (p.right == null && p.left == null) {
            shift(parent,p,null);
        }else{
            //存在左子节点和右子节点
            //1.1找被删除的几点的后继
            BSTNode<T, V> s = p.right;
            BSTNode<T, V> sParent = null;
            while (s.left!=null){
                sParent = s;
                s = s.left;
            }
            //后继节点为s
            if (sParent != p){
                //1.2当删除节点和后继节点不相邻时，处理后继节点的子树
                shift(sParent,p,p.right);
                s.right = p.right;
            }
            //1。3后继节点取代被删除节点
            shift(parent,p,s);
            s.left = p.left;
        }
        return p.value;
    }
    private void shift(BSTNode<T,V> parent,BSTNode<T,V> deleted,BSTNode<T,V> child){
        if (parent == null){
            root = child;
        }else if (deleted == parent.left){
            parent.left = child;
        }else{
            parent.right = child;
        }
    }

    public List<V> less(T key){
        ArrayList<V> result = new ArrayList<>();
        //中序遍历
        BSTNode<T, V> p = this.root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p!=null || !stack.isEmpty() ){
            if (p!=null){
                stack.push(p);
                //向左走
                p = p.left;
            }else{
                //弹出栈顶元素
                BSTNode<T,V> pop = stack.pop();
                //处理结果
                int i = key.compareTo(pop.key);
                if (i>0){
                    result.add(pop.value);
                }else {
                    //不成立退出循环
                    break;
                }
                //向右走
                p = pop.right;
            }
        }
        return result;
    }
    public List<V> greater(T key){
        /*ArrayList<V> result = new ArrayList<>();
        //中序遍历
        BSTNode<T, V> p = this.root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p!=null || !stack.isEmpty() ){
            if (p!=null){
                stack.push(p);
                //向左走
                p = p.left;
            }else{
                //弹出栈顶元素
                BSTNode<T,V> pop = stack.pop();
                //处理结果
                int i = key.compareTo(pop.key);
                if (i<0){
                    result.add(pop.value);
                }
                //向右走
                p = pop.right;
            }
        }
        return result;*/

        ArrayList<V> result = new ArrayList<>();
        //反向中序遍历
        BSTNode<T, V> p = this.root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p!=null || !stack.isEmpty() ){
            if (p!=null){
                stack.push(p);
                //向右走
                p = p.right;
            }else{
                //弹出栈顶元素
                BSTNode<T,V> pop = stack.pop();
                //处理结果
                int i = key.compareTo(pop.key);
                if (i<0){
                    result.add(pop.value);
                }else {
                    //不成立退出循环
                    break;
                }
                //向左走
                p = pop.left;
            }
        }
        return result;
    }
    public List<V> between(T key1,T key2){
        ArrayList<V> result = new ArrayList<>();
        //中序遍历
        BSTNode<T, V> p = this.root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p!=null || !stack.isEmpty() ){
            if (p!=null){
                stack.push(p);
                //向左走
                p = p.left;
            }else{
                //弹出栈顶元素
                BSTNode<T,V> pop = stack.pop();
                //处理结果
                int i1 = key1.compareTo(pop.key);
                int i2 = key2.compareTo(pop.key);
                if (i1<=0&&i2>=0){
                    result.add(pop.value);
                }else if (i2<0){
                    //不成立退出循环
                    break;
                }
                //向右走
                p = pop.right;
            }
        }
        return result;
    }
}
